package com.lwl.Algorithmic_data_structure.class10_11二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lwl
 * @Description 多叉树和二叉树的互转
 * 思路： 将多叉树的每一层，都按照 左 -> 右 -> 右 -> 右 -> 右。。。的形式保存在二叉树当中
 * 相当于将多叉树顺时针旋转45度
 * @date 2023/5/24 7:55
 */
public class Code03NTreeToBTree {

    public static class Node {

        public int val;

        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    public static class TreeNode {

        int val;

        TreeNode left;

        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private Node bTree2NTree(TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        return new Node(treeNode.val, recursiveGenerateChild(treeNode.left));
    }

    /**
     * 递归生成 左 -> 右 -> 右 -> 右 -> 右。。。（当前传入的节点就是左节点）
     * 这里递归思想体现的明显，把自己事情做好，递归的事情也就做好了
     */
    private List<Node> recursiveGenerateChild(TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }
        List<Node> nodes = new ArrayList<>();
        while (treeNode != null) {
            Node node = new Node(treeNode.val, recursiveGenerateChild(treeNode.left));
            nodes.add(node);
            treeNode = treeNode.right;
        }
        return nodes;
    }

    private TreeNode nTree2BTree(Node node) {
        if (node == null) {
            return null;
        }
        TreeNode head = new TreeNode(node.val);
        head.left = recursiveGenerateLeft(node.children);
        return head;
    }

    /**
     * 将多叉树的一层放入二叉树的 左 -> 右 -> 右 -> 右 -> 右。。。
     */
    private TreeNode recursiveGenerateLeft(List<Node> children) {
        if (children == null || children.isEmpty()) {
            return null;
        }
        TreeNode head = null;
        for (Node child : children) {
            TreeNode node = new TreeNode(child.val);
            if (head == null) {
                head = node;
            } else {
                head.right = node;
            }
            // 一次循环中：第一次是递归生成左节点，然后就是递归生成左节点的右 -> 右 -> 右 。。。
            node.left = recursiveGenerateLeft(child.children);
        }
        return head;
    }
}
